#ifndef TREE_TREE_TREE_H
#define TREE_TREE_TREE_H

#include "TreeNode.h"
#include "LinkQueue.h"

template<typename Type> 
class Tree
{
public:
	Tree():m_proot(NULL), m_pcurrent(NULL){}
public:
	TreeNode<Type> *GetCurrent()
	{	//Get the current node
		return m_pcurrent;
	}
	void SetCurrent(TreeNode<Type> *current)
	{	//set the current node
		m_pcurrent = current;
	}
	bool Insert(Type item);		//insert an new node to current node
	void Remove(Type item);		//delete the node whose data is equal to item
	void Remove(TreeNode<Type> *current);	//delete the node
	bool Find(Type item);		//find the node whose data is equal to item
	void PrintChild(TreeNode<Type> *current);	//print the child tree
	TreeNode<Type> *Parent(TreeNode<Type> *current);	//get the parent

	void Print();				//print the tree
	void PreOrder(TreeNode<Type> *root);	//ordering the tree by visiting the root first
	void PostOrder(TreeNode<Type> *root);	//ordering the tree by visiting the root last
	void LevelOrder(TreeNode<Type> *root);	//ordering the tree by level
	void PreOrder();
	void PostOrder();
	void LevelOrder();

private:
	TreeNode<Type> *m_proot,*m_pcurrent;	
	bool Find(TreeNode<Type> *root, Type item);
	void Remove(TreeNode<Type> *root, Type item);
	TreeNode<Type> *Parent(TreeNode<Type> *root, TreeNode<Type> *current);
	void Print(TreeNode<Type> *start, int n=0);
};

template<typename Type> 
bool Tree<Type>::Insert(Type item)
{
	TreeNode<Type> *newnode = new TreeNode<Type>(item);
	if (NULL == newnode)
	{
		cout << "Application Error!" <<endl;
		exit(1);
	}
	if (NULL == m_proot)
	{
		m_proot = newnode;
		m_pcurrent = m_proot;
		return 1;
	}
	if (NULL == m_pcurrent)
	{
		cerr << "insert error!" <<endl;
		return 0;
	}

	if(NULL == m_pcurrent->m_pfirst)
	{
		m_pcurrent->m_pfirst = newnode;
		m_pcurrent = newnode;
		return 1;
	}
	TreeNode<Type> *pmove = m_pcurrent->m_pfirst;
	while(pmove->m_pnext)
	{
		pmove = pmove->m_pnext;
	}
	pmove->m_pnext = newnode;
	m_pcurrent = newnode;
	return 1;

}

template<typename Type> 
void Tree<Type>::Remove(TreeNode<Type> *current)
{
	if(NULL == current)
	{
		return;
	}
	TreeNode<Type> *temp = Parent(current);
	if(NULL == temp)
	{
		TreeNode<Type> *pmove = current->m_pfirst;
		if(NULL != pmove->m_pfirst)
		{
			pmove=pmove->m_pfirst;
			while(pmove->m_pnext)
			{
				pmove = pmove->m_pnext;
			}
			pmove->m_pnext = current->m_pfirst->m_pnext;
			current->m_pfirst->m_pnext = NULL;
		}
		else
		{
			pmove->m_pfirst = pmove->m_pnext;
		}
		m_proot = current->m_pfirst;
	}
	else
	{
		if(temp->m_pfirst == current)
		{
			TreeNode<Type> *pmove = current->m_pfirst;
			if (pmove)
			{
				while (pmove->m_pnext)
				{
					pmove = pmove->m_pnext;
				}
				pmove->m_pnext = current->m_pnext;
			}
			else
			{
				current->m_pfirst = current->m_pnext;
			}

		}
		else
		{
			TreeNode<Type> *pmove = temp->m_pfirst;
			while(pmove->m_pnext != current)
			{
				pmove = pmove->m_pnext;
			}
			pmove->m_pnext = current->m_pnext;
			while(pmove->m_pnext)
			{
				pmove = pmove->m_pnext;
			}
			pmove->m_pnext = current->m_pfirst;
		}
	}
	delete current;
}

template<typename Type> 
void Tree<Type>::Remove(TreeNode<Type> *root, Type item)
{
	if(NULL == root)
	{
		return;
	}
	if(root->m_pfirst)
	{
		TreeNode<Type> *pmove=root->m_pfirst;
		while(pmove)
		{
			Remove(pmove, item);
			pmove = pmove->m_pnext;
		}
	}	
	if(root->m_data == item)
	{
		Remove(root);
	}

}
template<typename Type> 
void Tree<Type>::Remove(Type item)
{
	return Remove(m_proot, item);
}

template<typename Type> 
TreeNode<Type>* Tree<Type>::Parent(	TreeNode<Type> *root, TreeNode<Type> *current)
{
		if(NULL == root)
		{
			return NULL;
		}
		TreeNode<Type> *pmove=root->m_pfirst,*temp;
		if(NULL != pmove)
		{
			while(pmove)
			{
				if(pmove == current)
				{
					return root;
				}
				pmove = pmove->m_pnext;
			}
		}
		pmove = root->m_pfirst;
		while(pmove)
		{
			temp = Parent(pmove, current);
			if(temp)
			{
				return temp;
			}
			pmove = pmove->m_pnext;
		}
		return NULL;
}

template<typename Type> 
TreeNode<Type>* Tree<Type>::Parent(TreeNode<Type> *current)
{
	return Parent(m_proot,current);
}

template<typename Type> 
void Tree<Type>::PrintChild(TreeNode<Type> *current)
{
	TreeNode<Type> *pmove = current->m_pfirst;
	cout<<"first";
	if(NULL != pmove)
	{
		cout<<"--->"<<pmove->m_data;
	}
	while(pmove->m_pnext)
	{
		cout<<"--->"<<pmove->m_data;
		pmove = pmove->m_pnext;
	}
}

template<typename Type> 
bool Tree<Type>::Find(TreeNode<Type> *root, Type item)
{
	if (root->m_data == item)
	{
		return 1;
	}
	if (NULL == root)
	{
		return 0;
	}
	TreeNode<Type> *pmove=root->m_pfirst;
	if (NULL == pmove)
	{
		return 0;
	}
	while (pmove)
	{
		if (Find(pmove, item))
		{
			return 1;
		}
		pmove = pmove->m_pnext;
	}
	return 0;
}

template<typename Type> 
bool Tree<Type>::Find(Type item)
{
	return Find(m_proot,item);
}

template<typename Type> 
void Tree<Type>::Print(TreeNode<Type> *start, int n = 0)
{
	if (NULL == start)
	{
		for (int i=0; i<n; i++)
		{
			cout << "     ";
		}
		cout << "NULL" << endl;
		return;
	}
	TreeNode<Type> *pmove = start->m_pfirst;
	Print(pmove, n+1);

	for (int i=0; i<n; i++)
	{
		cout << "     ";
	}
	cout << start->m_data << "--->" <<endl;

	if (NULL == pmove)
	{  
		return;
	}
	pmove = pmove->m_pnext;
	while (pmove)
	{
		Print(pmove, n+1);
		pmove = pmove->m_pnext;
	}
}

template<typename Type> 
void Tree<Type>::Print()
{
	Print(m_proot);
}

template<typename Type> 
void Tree<Type>::PreOrder(TreeNode<Type> *root)
{
	if (NULL == root)
	{
		return;
	}
	cout << root->m_data;
	TreeNode<Type> *pmove = root->m_pfirst;
	while (pmove)
	{
		PreOrder(pmove);
		pmove = pmove->m_pnext;
	}
}

template<typename Type> 
void Tree<Type>::PostOrder(TreeNode<Type> *root)
{
	if (NULL == root)
	{
		return;
	}
	TreeNode<Type> *pmove = root->m_pfirst;
	while (pmove)
	{
		PostOrder(pmove);
		pmove = pmove->m_pnext;
	}
	cout << root->m_data;
}

template<typename Type> 
void Tree<Type>::PreOrder()
{
	PreOrder(m_proot);
}

template<typename Type> 
void Tree<Type>::PostOrder()
{
	PostOrder(m_proot);
}

template<typename Type> 
void Tree<Type>::LevelOrder(TreeNode<Type> *root)
{	//using queue
	LinkQueue<TreeNode<Type> *> queue;
	TreeNode<Type> *pmove, *ptemp;
	if (root != NULL)
	{
		queue.Append(root);
		while (!queue.IsEmpty())
		{
			ptemp = queue.Delete();
			cout << ptemp->m_data;
			pmove = ptemp->m_pfirst;
			while(pmove)
			{
				queue.Append(pmove);
				pmove = pmove->m_pnext;
			}
		}
	}
}

template<typename Type> 
void Tree<Type>::LevelOrder()
{
	LevelOrder(m_proot);
}

#endif